package com.ly.algorithm.offerpointer;


import java.util.ArrayDeque;

public class TreeNode {
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int x) { val = x; }

       public void preOrder(TreeNode treeNode) {
       	    System.out.print(treeNode.val+" ");
       	    if(treeNode.left!=null)
				preOrder(treeNode.left);
       	    if(treeNode.right!=null)
				preOrder(treeNode.right);
       }

       //3,9,20,null,null,15,7
       public static TreeNode init(int[] arr) {
       	   if(arr.length == 0) {
       	   	    return null;
           }
	       ArrayDeque<TreeNode> queue = new ArrayDeque<>();
       	   TreeNode root = new TreeNode(arr[0]);
	       queue.add(root);
	       int i = 1;
	       while (true) {
               if(i>=arr.length) {
                   break;
               }
		       TreeNode pop = queue.pop();
		       if(arr[i] == -1) {
			       pop.left = null;
		       } else {
			       pop.left = new TreeNode(arr[i]);
			       queue.add(pop.left);
		       }
		       i++;
		       if(arr[i] == -1) {
			       pop.right = null;
		       } else {
			       pop.right = new TreeNode(arr[i]);
			       queue.add(pop.right);
		       }
		       i++;
	       }
	       return root;
       }

       //  1
	   // 2  3
	   //4
       public static void main(String[] args) {
           TreeNode treeNode = new TreeNode(1);
           treeNode.left = new TreeNode(2);
	       treeNode.right = new TreeNode(3);
	       treeNode.left.left = new TreeNode(4);
	       treeNode.left.right = new TreeNode(5);
           TreeNode init = init(new int[]{1, 2, 3, 4, 5, -1, -1});
           init.preOrder(init);
           treeNode.preOrder(treeNode);
       }
}